#include <bits/stdc++.h>
using namespace std;
/* 删除单链表的倒数第k个元素
 */
typedef struct lnode
{
    int data;
    struct lnode *next;
} lnode, *linklist;

int a[] = {1, 2, 3, 4, 5, 6, 7, 8};

// 尾插法建立单链表的算法
void createlist(linklist &l)
{
    l = (linklist)malloc(sizeof(lnode));
    l->next = NULL;
    lnode *r = l, *s;
    for (int i = 0; i < sizeof(a) / sizeof(int); i++)
    {
        s = (lnode *)malloc(sizeof(lnode));
        s->data = a[i];
        s->next = NULL;
        r->next = s;
        r = s;
    }
    r->next = NULL;
}
void printlist(linklist L)
{
    lnode *s = L->next;
    while (s)
    {
        cout << s->data << " ";
        s = s->next;
    }
    cout << endl;
}
// 删除倒数第k个元素
/* 算法思想：
    设置指针pre指向头结点，指针p和q指向第一个元素，开始时指针q向后扫描k个位置，
    然后p和q同时向后扫描当q到达最后一个位置时p恰好在倒数第k个位置，pre恰好就是p的前驱，
    此时删除p即可
    */
void del(linklist &l, int k)
{
    lnode *pre = l, *p = pre->next, *q = p;
    // q向后扫描k个位置
    for (int i = 0; i < k; i++)
    {
        q = q->next;
    }
    // 当q没到最后一个元素时所有指针向后扫描
    while (q)
    {
        pre = pre->next;
        p = p->next;
        q = q->next;
    }
    // 删除p指针指向的结点
    pre->next = p->next;
    free(p);
}
int main(int argc, char const *argv[])
{
    linklist l;
    createlist(l);
    cout << "数组长度为" << sizeof(a) / sizeof(int) << endl;
    cout << "链表为" << endl;
    printlist(l);
    int k;
    cin >> k;
    while (k != 999)
    {
        del(l, k);
        cout << "删除后的链表为 ";
        printlist(l);
        cin >> k;
    }

    system("pause");
    return 0;
}
